/**
 * Created by mxy
 */

var jsonFileSet = [
    'data/test.json',
    'data/miserables.json',
    'data/4-complete.json',
    'data/5-complete.json',
    'data/centaurus.json',
    'data/radial.json',
    'data/triangleMesh.json',
    'data/quadrilateralMesh.json',
    'data/quadrilateralSimple.json'
];
var jsonFile;

d3.select('#dataset')
    .selectAll('option')
    .data(jsonFileSet)
    .enter().append('option')
    .attr('value', function (d, i) {
        return i;
    }).html(function (d) {
        return d;
    });
$('#datasetconfirm').click(function (e) {
    var ds = document.getElementById("dataset");
    changeDataSet(ds.selectedIndex);
});
function changeDataSet(index) {
    "use strict";
    document.getElementById("dataset").selectedIndex = index;
    jsonFile = jsonFileSet[index];
    initialize(true);
}

$(document).ready(function () {
    changeDataSet(0);
});

var jq = window.jQuery;
var d3 = window.d3;
var console = window.console;
var errout = document.getElementById('debug');
var svg = d3.select('#svg_canvas');
var svg_dom = document.getElementById('svg_canvas');
var graphData;

var svg_size = {
    width: 960,
    height: 540
};

svg_dom.setAttribute("width", svg_size.width);
svg_dom.setAttribute("height", svg_size.height);

var svg_padding = 25;

var randomizePosition = false;
var randomize_dom = document.getElementById('randomize');
randomize_dom.checked = randomizePosition;

var color = d3.scaleOrdinal(d3.schemeCategory20);

// Returns a random integer between min (included) and max (excluded)
// Using Math.round() will give you a non-uniform distribution!
function getRandomInt(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    return Math.floor(Math.random() * (max - min)) + min;
}

// Timer Function.
var curTimer = new Date();
var totalTime_dom = document.getElementById('totalTime');
var totalTime = 0;
function startTimer() {
    curTimer = new Date();
}
function stopTimer() {
    nowTimer = new Date();
    var during = nowTimer.getTime() - curTimer.getTime();
    totalTime += during / 1000;
    totalTime = Math.round(totalTime*1000) / 1000;
    totalTime_dom.innerHTML = 'total time: ' + totalTime + ' seconds';
}

// --------------------------------------------------------------------------------------------------------------------
// In JavaScript, how to define a
// class?

// this is a constructor
function ___class() {
    // (public) object property
    this.___objectProperty = 'object property';
};

// static property
___class.___classProperty = 'class property';

// class function
___class.___classFunction = function () {
    return 'class function';
};

// object function
___class.prototype.___objectFunction = function () {
    return "object function";
};
// --------------------------------------------------------------------------------------------------------------------


// Define a Node class
function Node() {
    this.value = this.x = this.y = 0;
    this.name = '';
    this.group = 0;
    this.in = new Array();
    this.out = new Array();
};

// --------------------------------------------------------------------------------------------------------------------

// Define a Link class
function Link() {
    this.src = 0;
    this.dst = 0;
    this.value = 0;
};

// --------------------------------------------------------------------------------------------------------------------

var nodelist;
var linklist;


function initializeGraph() {
    nodelist = new Array();
    linklist = new Array();

    svg.selectAll('g')
        .data([])
        .exit().remove();
    svg.selectAll('line')
        .data([])
        .exit().remove();
    svg.selectAll('circle')
        .data([])
        .exit().remove();

    var node_length = graphData.nodes.length;
    var N_1 = Math.floor(Math.sqrt(node_length));
    var N_2 = N_1 + 1;
    var center = {
        x: svg_size.width / 2,
        y: svg_size.height / 2
    };
    var scope = {
        xmin: svg_padding,
        xmax: svg_size.width - svg_padding,
        ymin: svg_padding,
        ymax: svg_size.height - svg_padding
    };
    randomizePosition = randomize_dom.checked;
    // parse the node data
    graphData.nodes.forEach(function (element, index, array) {
        var n = new Node();
        var x, y;
        if (randomizePosition) {
            x = getRandomInt(scope.xmin, scope.xmax);
            y = getRandomInt(scope.ymin, scope.ymax);
        } else {
            x = index % N_2 * 20 + center.x;
            y = Math.floor(index / N_2) * 20 + center.y;
        }
        n.x = x;
        n.y = y;
        n.name = element.id;
        n.group = element.group;
        nodelist.push(n);
    });

    // parse the link data
    graphData.links.forEach(function (element, index, array) {
        var l = new Link();
        var i;
        for (i = 0;i<node_length;i++) {
            if (nodelist[i].name === element.source) {
                break;
            }
        }
        if (i === node_length) {
            console.log('Bad link. (source error)' + element.source);
            return ;
        }
        l.src = i;
        for (i = 0;i<node_length;i++) {
            if (nodelist[i].name === element.target) {
                break;
            }
        }
        if (i === node_length) {
            console.log('Bad link. (target error)' + element.target);
            return ;
        }
        l.dst = i;
        nodelist[l.src].out.push(l.dst);
        nodelist[l.dst].in.push(l.src);
        l.value = element.value;
        linklist.push(l);
    });
}

function drawGraph() {
    "use strict";
    var blank_rect = svg.append("g")
        .append("rect")
        .attr("x", 0).attr("y", 0)
        .attr("width", svg_size.width)
        .attr("height", svg_size.height)
        .attr("fill", "white")
        .on("mouseover", hoverOutCircle);

    // 在SVG中创建nodes和lines，注意先后次序
    var lines = svg.append("g")
        .attr("class", "links")
        .selectAll("line")
        .data(linklist/*graphData.links*/)
        .enter().append("line")
        .attr("class", "link")
        .attr("stroke-width", function (d) {
            return d.value;
        })
        .attr("x1", function (d) {
            return nodelist[d.src].x;
        })
        .attr("y1", function (d) {
            return nodelist[d.src].y;
        })
        .attr("x2", function (d) {
            return nodelist[d.dst].x;
        })
        .attr("y2", function (d) {
            return nodelist[d.dst].y;
        });
    var nodes = svg.append("g")
        .attr("class", "nodes")
        .selectAll("circle")
        .data(nodelist/*graphData.nodes*/)
        .enter().append("circle")
        .attr("class", "node")
        .attr("fill", function (d) {
            return color(d.group);
        }).attr("cx", function (d) {
            return d.x;
        }).attr("cy", function (d) {
            return d.y;
        }).on('mouseover', hoverCircle);
}

var tooltip = document.getElementById('tooltip');
var tooltip_offset = 30;
function hoverCircle(d) {
    tooltip.style.left = (mouse_position.x + tooltip_offset) + 'px';
    tooltip.style.top = (mouse_position.y + tooltip_offset) + 'px';
    tooltip.innerHTML = "name: " + d.name + "<\/br>group: " + d.group + "<\/br>value: " + d.value;
    tooltip.style.visibility = 'visible';
}
function hoverOutCircle(d) {
    tooltip.style.visibility = 'hidden';
}

function updateGraph() {
    "use strict";
    // 在SVG中创建nodes和lines，注意先后次序
    var lines = svg.select(".links")
        .selectAll("line")
        .data(linklist/*graphData.links*/)
        .attr("stroke-width", function (d) {
            return d.value;
        })
        .attr("x1", function (d) {
            return nodelist[d.src].x;
        })
        .attr("y1", function (d) {
            return nodelist[d.src].y;
        })
        .attr("x2", function (d) {
            return nodelist[d.dst].x;
        })
        .attr("y2", function (d) {
            return nodelist[d.dst].y;
        });
    var nodes = svg.select(".nodes")
        .selectAll("circle")
        .data(nodelist/*graphData.nodes*/)
        .attr("fill", function (d) {
            return color(d.group);
        }).attr("cx", function (d) {
            return d.x;
        }).attr("cy", function (d) {
            return d.y;
        });
}

function initialize(refresh) {
    "use strict";
    totalTime = 0;
    natural_convergent = false;
    errout.innerHTML = '';

    if (refresh) {
        jq.ajax(jsonFile).done(function(data) {
            graphData = data;
            // errout.innerHTML += 'Info: Success to get the graph data. <\/br>Open the dev tool to explore it. <\/br>';
            subInitialize();
        }).fail(function() {
            // errout.innerHTML += 'Err: Fail to get the graph data. <\/br>';
        });
    } else {
        subInitialize();
    }

    function subInitialize() {
        initializeGraph();

        calibrate();

        drawGraph();
    }
}

// 指示是否自然收敛
var natural_convergent;
function OriginalFDLayout() {
    "use strict";
    var i, j;

    var node1, node2, dx, dy, fx, fy, distance, distanceSquared, force, s, visible, xmean, ymean, x, y;

    var MAX_DISPLACEMENT_SQUARED = 50;  // 50

    // Convergent value
    var CONVERGENT_VALUE = 4;
    // Convergent times
    var CONVERGENT_MAX_TIMES = 50000; // 50000
    var convergent_iterations = 0;
    var iterations_dom = document.getElementById('iterations');
    // Convergent indicator
    var convergent_indicator;
    var CONVERGENT_MOVEMENT = 0.01;

    // spring rest length
    var L = 130; // 130
    // 试验尝试得知，K_r应该比K_s大很多个数量级，才能有比较好的效果。
    // repulsive force constant
    var K_r = 1000000; // 1000000
    // spring constant
    var K_s = 0.5; // 0.5
    // time step
    var delta_t = 0.015625; // 0.015625

    var node1_inout = new Array();

    var center = {
        x: svg_size.width / 2,
        y: svg_size.height / 2
    };

    var N = nodelist.length;

    for (convergent_iterations = 0; convergent_iterations < CONVERGENT_MAX_TIMES && !convergent_indicator; convergent_iterations++) {
        // initialize net forces
        for (i = 0;i<N;i++) {
            nodelist[i].force_x = 0;
            nodelist[i].force_y = 0;
        }

        convergent_indicator = true;
        iterations_dom.innerHTML = 'iterations: ' + convergent_iterations;

        // repulsion between all pairs
        for (i = 0; i < N - 1;i++) {
            // shallow copy
            node1 = nodelist[i];
            for (j = i + 1; j < N; j++) {
                node2 = nodelist[j];
                dx = node2.x - node1.x;
                dy = node2.y - node1.y;
                if (dx !== 0 || dy !== 0) {
                    distanceSquared = dx * dx + dy * dy;
                    distance = Math.sqrt(distanceSquared);
                    force = K_r / distanceSquared;
                    fx = force * dx / distance;
                    fy = force * dy / distance;
                    node1.force_x = node1.force_x - fx;
                    node1.force_y = node1.force_y - fy;
                    node2.force_x = node2.force_x + fx;
                    node2.force_y = node2.force_y + fy;
                }else{
                    fx = 0.05;
                    fy = 0.04;
                    node1.force_x = node1.force_x - fx;
                    node1.force_y = node1.force_y - fy;
                    node2.force_x = node2.force_x + fx;
                    node2.force_y = node2.force_y + fy;
                }
            }
        }

        // spring force between adjacent pairs
        for (i = 0; i < N;i++) {
            // shallow copy
            node1 = nodelist[i];
            node1_inout = node1.in.concat(node1.out);
            for (j = 0; j < node1_inout.length; j++) {
                node2 = nodelist[node1_inout[j]];
                if (i < node1_inout[j]) {
                    dx = node2.x - node1.x;
                    dy = node2.y - node1.y;
                    if (dx !== 0 || dy !== 0) {
                        distanceSquared = dx * dx + dy * dy;
                        distance = Math.sqrt(distanceSquared);
                        force = K_s * (distance - L);
                        fx = force * dx / distance;
                        fy = force * dy / distance;
                        node1.force_x = node1.force_x + fx;
                        node1.force_y = node1.force_y + fy;
                        node2.force_x = node2.force_x - fx;
                        node2.force_y = node2.force_y - fy;
                    }
                }
            }
        }
        var previous_x=new Array();
        var previous_y=new Array();
        // update positions
        for (i = 0;i<N;i++) {
            node1 = nodelist[i];
            dx = delta_t * node1.force_x;
            dy = delta_t * node1.force_y;
            distanceSquared = dx * dx + dy * dy;
            if (distanceSquared > MAX_DISPLACEMENT_SQUARED) {
                s = Math.sqrt(MAX_DISPLACEMENT_SQUARED / distanceSquared);
                dx = dx * s;
                dy = dy * s;
            }
            node1.x += dx;
            node1.y += dy;

            // judge the convergency
            dx = (dx > 0)? dx: -dx ;
            dy = (dy > 0)? dy: -dy ;
            if (dx + dy > CONVERGENT_MOVEMENT) {
                 convergent_indicator = false;
            }
        }
        
    }

    iterations_dom.innerHTML = 'iterations: ' + convergent_iterations ;
    if (convergent_indicator) {
        natural_convergent = true;
        errout.innerHTML += '小角度个数：' + countSmallAngle() + '；相交线段个数：' + countCrossingLines() + '<\/br>';
        calibrate();
    } else {
        // 测试顶点是否都移到了场景之外，如果是，将顶点移回场景中
        visible = false;
        for (i=0;i<N;i++) {
            node1 = nodelist[i];
            x = node1.x;
            y = node1.y;
            if (0 <= x && x < svg_size.width && 0 <= y && y < svg_size.height) {
                visible = true;
                break;
            }
        }
        if (!visible) {
            // 求质心
            xmean = 0;
            ymean = 0;
            for (i=0;i<N;i++) {
                node1 = nodelist[i];
                xmean += node1.x;
                ymean += node1.y;
            }
            xmean /= N;
            ymean /= N;
            // 将质心OM平移到中心位置OC，每个坐标OA变换之后的坐标 OB = OA + MC = OA + OC - OM
            errout.innerHTML += '执行了一次质心移中。<\/br>';
            for (i=0;i<N;i++) {
                node1 = nodelist[i];
                node1.x += center.x - xmean;
                node1.y += center.y - ymean;
            }
        }
    }
}

function heuristicFDLayout() {
    "use strict";
    var tmp_randomizePosition = randomize_dom.checked;
    var i, j;
    // 随机尝试的迭代次数
    var N = 5;
    var N2 = 0;
    var curLinklist = [];
    var curNodelist = [];
    var minVal = +INIFINITY;
    var target = 0;
    startTimer();
    // 禁用随机模式
    randomizePosition = false;
    randomize_dom.checked = false;
    initialize(false);
    while (!natural_convergent) {
        OriginalFDLayout();
    }
    target = countSmallAngle() + countCrossingLines() * 2;
    if (minVal > target) {
        minVal = target;
        // 深拷贝
        jq.extend(true, curLinklist, linklist);
        jq.extend(true, curNodelist, nodelist);
    }
    // 启用随机模式
    randomizePosition = true;
    randomize_dom.checked = true;
    for(i=0;i<N;i++) {
        initialize(false);
        while (!natural_convergent) {
            OriginalFDLayout();
        }
        target = countSmallAngle() + countCrossingLines() * 2;
        if (minVal > target) {
            minVal = target;
            // 深拷贝
            jq.extend(true, curLinklist, linklist);
            jq.extend(true, curNodelist, nodelist);
        }
    }
    // 深拷贝
    jq.extend(true, linklist, curLinklist);
    jq.extend(true, nodelist, curNodelist);

    stopTimer();
    updateGraph();
    errout.innerHTML = '小角度个数：' + countSmallAngle() + '；相交线段个数：' + countCrossingLines() + '<\/br>';
    // 恢复之前的随机模式设置
    randomizePosition = tmp_randomizePosition;
    randomize_dom.checked = tmp_randomizePosition;
}

// 标定
var INIFINITY = 1000000;
var MINSCALE = 5;
var MAXSCALE = 60;
function calibrate() {
    "use strict";
    var xmin = +INIFINITY, xmax = -INIFINITY, ymin = +INIFINITY, ymax = -INIFINITY;
    var N = nodelist.length;
    var i, j, x, y;
    // var xmean = 0.0, ymean = 0.0;

    // 第一次遍历，找出点在坐标X的最值、平均值，以及点在坐标Y的最值、平均值
    for (i = 0; i<N ; i++) {
        x = nodelist[i].x;
        y = nodelist[i].y;

        xmin = (x < xmin)?  x : xmin;
        xmax = (x > xmax)?  x : xmax;

        ymin = (y < ymin)?  y : ymin;
        ymax = (y > ymax)?  y : ymax;
        //
        // xmean += x * 1.0;
        // ymean += y * 1.0;
    }
    // xmean /= N;
    // ymean /= N;

    // 找出目标X和目标Y的值域
    var rangeX, rangeY, kx, ky;
    var rangeBound = {
        xlower: 200,
        xupper: svg_size.width - svg_padding * 2,
        ylower: 200,
        yupper: svg_size.height - svg_padding * 2
    };
    if (N < MINSCALE) {
        rangeX = rangeBound.xlower;
        rangeY = rangeBound.ylower;
    } else if (N > MAXSCALE) {
        rangeX = rangeBound.xupper;
        rangeY = rangeBound.yupper;
    } else {
        kx = (rangeBound.xupper - rangeBound.xlower) / (MAXSCALE - MINSCALE);
        rangeX = rangeBound.xlower + kx * (N - MINSCALE);
        ky = (rangeBound.yupper - rangeBound.ylower) / (MAXSCALE - MINSCALE);
        rangeY = rangeBound.ylower + ky * (N - MINSCALE);
    }
    rangeX = Math.round(rangeX);
    rangeY = Math.round(rangeY);
    // errout.innerHTML += 'rangX' + rangeX + '   rangY' + rangeY;

    kx = rangeX / (xmax - xmin);
    ky = (ymax - ymin < 0.01) ? 0 : rangeY / (ymax - ymin);
    var rxmin = Math.round((svg_size.width - rangeX) / 2);
    var rymin = Math.round((svg_size.height - rangeY) / 2);
    // 第二次遍历，对所有坐标进行归一化
    for (i = 0; i<N ; i++) {
        nodelist[i].x = kx * (nodelist[i].x - xmin) + rxmin;
        nodelist[i].y = ky * (nodelist[i].y - ymin) + rymin;
    }
}

$('#svg_canvas').click(function () {
    calc();
});

$(document).keydown(function (e) {
    if (e.which === "C".charCodeAt(0)) {
        calc();
    } else if (e.which === "R".charCodeAt(0)) {
        initialize(false);
    } else if (e.which === "H".charCodeAt(0)) {
        heuristicFDLayout();
    }
});

function calc() {
    // 如果已经达到自然收敛状态，停止计算
    if (natural_convergent) {
        return;
    }

    startTimer();
    OriginalFDLayout();
    updateGraph();
    stopTimer();
}


var mouse_position = {
    x: 0,
    y: 0
};

$(document).mousemove(function() {
    mouse_position.x = event.pageX;
    mouse_position.y = event.pageY;
});

$('#reset').click(function () {
    initialize(false);
});

// 根据当前的nodelist和linklist，统计小角度的个数
var SMALLANGLE = Math.PI * (20 / 180);
function countSmallAngle() {
    var i, j, node1, node1_inout, angleList, x, y, curAngle;
    var N = nodelist.length;
    var N2;
    var ret = 0;
    for (i=0;i<N;i++) {
        // 遍历当前节点的邻接节点，计算出角度并且入栈
        node1 = nodelist[i];
        node1_inout = node1.in.concat(node1.out);
        // 对于当前节点，至少要有两个邻接节点
        N2 = node1_inout.length;
        if (N2 >= 2) {
            angleList = new Array();
            for (j=0;j<N2; j++) {
                x = nodelist[node1_inout[j]].x - node1.x;
                y = nodelist[node1_inout[j]].y - node1.y;
                curAngle = Math.atan2(y,x);
                curAngle = (curAngle < 0) ? (curAngle + Math.PI * 2): curAngle;
                angleList.push(curAngle);
            }
            // 排序
            angleList.sort();
            // 计数小角度的个数
            for (j=0;j<N2-1;j++) {
                if (angleList[j+1] - angleList[j] < SMALLANGLE) {
                    ret++;
                }
            }
            if (angleList[0] + Math.PI * 2 - angleList[N2 - 1] < SMALLANGLE) {
                ret++;
            }
        }
    }
    return ret;
}

// 根据当前的nodelist和linklist，统计相交线段的交点个数
function countCrossingLines() {
    var i, j, node1, node2, node3, node4, x, y, k;
    var N = nodelist.length;
    var N2 = linklist.length;
    var ret = 0;
    for (i=0;i<N2-1;i++) {
        node1 = nodelist[linklist[i].src];
        node2 = nodelist[linklist[i].dst];
        for (j=i+1;j<N2;j++) {
            node3 = nodelist[linklist[j].src];
            node4 = nodelist[linklist[j].dst];
            if (segmentsIntersect(node1, node2, node3, node4)) {
                ret++;
            }
        }
    }
    return ret;
}

// 计算几何：相交线段的判定。参考《算法导论》
function direction(pi, pj, pk) {
    return ( (pk.x - pi.x) * (pj.y - pi.y) - (pj.x - pi.x) * (pk.y - pi.y) );
}
// 计算几何：相交线段的判定。参考《算法导论》
function segmentsIntersect(p1, p2, p3, p4) {
    var d1 = direction(p3, p4, p1);
    var d2 = direction(p3, p4, p2);
    var d3 = direction(p1, p2, p3);
    var d4 = direction(p1, p2, p4);
    if ( ((d1>0 && d2<0) || (d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0)) ) {
        return true;
    }
    return false;
}